package com.berchen.test;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 将复杂 链表进行复制
 */
public class CopyFZLinked {

    public static void main(String[] args) {
        RandomListNode head=new RandomListNode(1);
        RandomListNode node2=new RandomListNode(2);
        RandomListNode node3=new RandomListNode(3);
        RandomListNode node4=new RandomListNode(4);
        RandomListNode node5=new RandomListNode(5);
        RandomListNode random3=new RandomListNode(3);
        RandomListNode random5=new RandomListNode(5);
        RandomListNode random_1=new RandomListNode(-1);
        RandomListNode random2=new RandomListNode(2);
        RandomListNode random_2=new RandomListNode(-1);
        head.next=node2;
        node2.next=node3;
        node3.next=node4;
        node4.next=node5;
        node5.next=random3;
        random3.next=random5;
        random5.next=random_1;
        random_1.next=random2;
        random2.next=random_2;

        CopyFZLinked copyFZLinked = new CopyFZLinked();
        RandomListNode clone = copyFZLinked.Clone(head);
        while (clone!=null){
            System.out.println(clone+"  "+clone.random);
            clone=clone.next;
        }
    }
    public RandomListNode Clone1(RandomListNode pHead){
        if(pHead == null) return null;
        RandomListNode cur = pHead;
        Map<RandomListNode,RandomListNode> map = new HashMap<>();
        // 3. 复制各节点，并建立 “原节点 -> 新节点” 的 Map 映射
        // 创建新的节点  这时候各个节点之间没有任何关系 只有新节点与来节点相同值构成一个对应关系
        while(cur != null) {
            map.put(cur, new RandomListNode(cur.label));
            cur = cur.next;
        }
        cur = pHead;
        // 4. 构建新链表的 next 和 random 指向
        while(cur != null) {
            // map.get(cur).next 新节点的next
            // map.get(cur.next); 老节点的下一个节点
            map.get(cur).next = map.get(cur.next);
            // map.get(cur).random 新节点的随机节点
            // map.get(cur.random); 老节点的随机节点   一一对应   如果老节点没有 那么新节点对应的就是null
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        // 5. 返回新链表的头节点
        return map.get(pHead);
    }

    /**
     * 自己写的
     * @param pHead
     * @return
     */
    public RandomListNode Clone(RandomListNode pHead) {

        RandomListNode head=new RandomListNode(-1);
        int count=0;    // 计算链表的长度
        RandomListNode temp=pHead;
        while(temp!=null){
            count++;
            temp=temp.next;
        }
        System.out.println(count);
        count=count/2;
        temp=pHead;
        RandomListNode[] arr=new RandomListNode[count];

        // 将前面真实节点 加入数组
        for(int i =0;i<count;i++){
            arr[i]=temp;
            temp=temp.next;
        }
        System.out.println(temp);
        int index=0;
        while(temp!=null){
            int mb=temp.label-1;
            if(mb>=0) {
                arr[index++].random = arr[mb];
            }
            temp = temp.next;
        }
        System.out.println(Arrays.toString(arr));
        temp=head;
        for(int i =0;i<arr.length;i++){
            temp.next=arr[i];
            temp=temp.next;
        }
        return head.next;
    }
}
 class RandomListNode {
    int label;
    RandomListNode next = null;
    RandomListNode random = null;

    RandomListNode(int label) {
        this.label = label;
    }

     @Override
     public String toString() {
         return "RandomListNode{" +
                 "label=" + label +
                 '}';
     }
 }
